#include "ExpensiveFirst.hh"
#include "structures.hh"

#include <vector>
#include <algorithm>
#include <iostream>

struct SortByCost {
  SortByCost ( Concert* concert, 
      unsigned int (*ptrGetMusicianCost)(Musician*, Concert*)) :
    concert_ ( concert ) ,
    ptrGetMusicianCost_ ( ptrGetMusicianCost )
  { }

  bool operator ()  ( Musician* m1, Musician* m2 ) {
    return (*ptrGetMusicianCost_)(m1, concert_) < (*ptrGetMusicianCost_)(m2, concert_);
  }

  private:
    Concert* concert_;
    unsigned int (*ptrGetMusicianCost_)(Musician*, Concert*);
};

std::vector< Piece* > ExpensiveFirst ( Concert* concert,
    unsigned int (*ptrGetMusicianCost)(Musician*, Concert*))
{
  std::vector< Piece* >* schedule 
    = new std::vector< Piece* > [concert->musicians.size()];
  unsigned int remainingPieces = concert->pieces.size();

  std::vector< Musician* > sortedMusicians ( concert->musicians );
  std::sort ( sortedMusicians.begin(), sortedMusicians.end(), 
      SortByCost(concert, ptrGetMusicianCost) );

  std::vector< Musician* >::const_iterator m;
  unsigned int i = 0;
  for ( m = sortedMusicians.begin(); 
      m != sortedMusicians.end() && remainingPieces > 0; 
      ++m, ++i ) {

    if ( i > 0 ) {
      std::vector< Piece* >::iterator p;
      for ( p = (*m)->pieces.begin(); p != (*m)->pieces.end(); ++p ) {
        std::vector< Piece* >::iterator p2 = 
          std::find ( schedule[i-1].begin(), schedule[i-1].end(), *p );

        // Est ce que la pièce est jouée juste avant
        if ( p2 != schedule[i-1].end() ) {
          std::swap ( *p2, schedule[i-1].at(schedule[i-1].size() - 1) );
        } else { // Est ce qu'il a déjà été joué

          bool everPlayed = false;
          for ( unsigned int k = 0; k < i - 1 && everPlayed == false; ++k ) {
          everPlayed |= 
            (std::find ( schedule[k].begin(), schedule[k].end(), *p ) 
             != schedule[k].end() );
          }
         
          if ( !everPlayed )
            schedule[i].push_back( *p ); 
        }

      }

    } else schedule[i].assign ( (*m)->pieces.begin(), (*m)->pieces.end() );

    remainingPieces -= schedule[i].size();
  }

  std::vector < Piece* > result;
  for ( unsigned int j = 0; j < i; ++j ) {
      std::vector< Piece* >::const_iterator p;
      for( p = schedule[j].begin(); p != schedule[j].end(); ++p )
        result.push_back( *p );
  }

  delete[] schedule;
  return result;
}
